{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chap1 Python Primer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:44:47.091368Z",
     "start_time": "2019-06-21T02:44:47.087858Z"
    }
   },
   "outputs": [],
   "source": [
    "import re\n",
    "from typing import List, TypeVar, Tuple, Any, Generator\n",
    "from random import randrange, randint\n",
    "Num = TypeVar('Num', int, float)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reinforcement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.1 \n",
    "Write a short Python function, is multiple(n, m), that takes two integer\n",
    "values and returns True if n is a multiple of m, that is, n = mi for some\n",
    "integer i, and False otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T14:46:53.647946Z",
     "start_time": "2019-06-20T14:46:53.644682Z"
    }
   },
   "outputs": [],
   "source": [
    "def is_multiple(n: int, m: int) -> bool:\n",
    "    return True if n % m == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T14:47:13.884194Z",
     "start_time": "2019-06-20T14:47:13.874045Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_multiple(4, 2), is_multiple(4, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.2\n",
    "Write a short Python function, is even(k), that takes an integer value and\n",
    "returns True if k is even, and False otherwise. However, your function\n",
    "cannot use the multiplication, modulo, or division operators.\n",
    "\n",
    "这个一开始是没有头绪的，看了hint: `Use bit operations.`, 仍然不会，最后参考[Check if a number is odd or even in python [duplicate]](https://stackoverflow.com/questions/21837208/check-if-a-number-is-odd-or-even-in-python)得到答案。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:04:03.820370Z",
     "start_time": "2019-06-20T15:04:03.811375Z"
    }
   },
   "outputs": [],
   "source": [
    "def is_even(k: int) -> bool:\n",
    "    return False if k & 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:04:04.302465Z",
     "start_time": "2019-06-20T15:04:04.295976Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_even(3), is_even(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.3\n",
    "Write a short Python function, minmax(data), that takes a sequence of\n",
    "one or more numbers, and returns the smallest and largest numbers, in the\n",
    "form of a tuple of length two. Do not use the built-in functions min or\n",
    "max in implementing your solution.\n",
    "\n",
    "注意下面的代码中不可以使用`Union[int, float]`， 参考[stackoverflow](https://stackoverflow.com/questions/43957034/python-type-hints-specifying-a-type-to-be-a-list-of-numbers-ints-and-or-floats)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:24:10.756558Z",
     "start_time": "2019-06-20T15:24:10.743317Z"
    }
   },
   "outputs": [],
   "source": [
    "# Num = TypeVar('Num', int, float)\n",
    "def minmax(data: List[Num]) -> Tuple[Num, Num]:\n",
    "    min_num = max_num = data[0]\n",
    "    for num in data:\n",
    "        if num < min_num:\n",
    "            min_num = num\n",
    "        if num > max_num:\n",
    "            max_num = num\n",
    "    return min_num, max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:24:18.708297Z",
     "start_time": "2019-06-20T15:24:18.693593Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 4)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minmax([1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.4, R-1.5\n",
    "1.4: Write a short Python function that takes a positive integer n and returns\n",
    "the sum of the squares of all the positive integers smaller than n.\n",
    "\n",
    "1.5: Give a single command that computes the sum from Exercise R-1.4, rely-\n",
    "ing on Python’s comprehension syntax and the built-in sum function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:30:54.521583Z",
     "start_time": "2019-06-20T15:30:54.516659Z"
    }
   },
   "outputs": [],
   "source": [
    "def sum_sq(n: int) -> int:\n",
    "    return sum(i*i for i in range(1, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:31:14.740944Z",
     "start_time": "2019-06-20T15:31:14.731115Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_sq(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.6, R-1.7\n",
    "R-1.6: Write a short Python function that takes a positive integer n and returns\n",
    "the sum of the squares of all the odd positive integers smaller than n.\n",
    "\n",
    "R-1.7: Give a single command that computes the sum from Exercise R-1.6, rely-\n",
    "ing on Python’s comprehension syntax and the built-in sum function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:32:18.028258Z",
     "start_time": "2019-06-20T15:32:18.017158Z"
    }
   },
   "outputs": [],
   "source": [
    "def sum_odd_sq(n: int) -> int:\n",
    "    return sum(i*i for i in range(1, n) if not is_even(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:32:25.802274Z",
     "start_time": "2019-06-20T15:32:25.793704Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_odd_sq(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.8\n",
    "Python allows negative integers to be used as indices into a sequence,\n",
    "such as a string. If string s has length n, and expression s[k] is used for in-\n",
    "dex −n ≤ k < 0, what is the equivalent index j ≥ 0 such that s[j] references\n",
    "the same element?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:40:13.143583Z",
     "start_time": "2019-06-20T15:40:13.133285Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# j = n + k <=> k = j - n\n",
    "def check(data: str='hello') -> bool:\n",
    "    n = len(data)\n",
    "    for j in range(n):\n",
    "        k = j - n\n",
    "        if data[j] != data[k]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "check()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.9 \n",
    "What parameters should be sent to the range constructor, to produce a\n",
    "range with values 50, 60, 70, 80?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:50:34.267076Z",
     "start_time": "2019-06-20T15:50:34.262705Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[50, 60, 70, 80]\n"
     ]
    }
   ],
   "source": [
    "print(list(range(50, 90, 10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.10\n",
    "What parameters should be sent to the range constructor, to produce a\n",
    "range with values 8, 6, 4, 2, 0, −2, −4, −6, −8?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:50:54.576141Z",
     "start_time": "2019-06-20T15:50:54.569138Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 6, 4, 2, 0, -2, -4, -6, -8]\n"
     ]
    }
   ],
   "source": [
    "print(list(range(8, -10, -2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.11\n",
    "Demonstrate how to use Python’s list comprehension syntax to produce\n",
    "the list [1, 2, 4, 8, 16, 32, 64, 128, 256]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:51:15.451914Z",
     "start_time": "2019-06-20T15:51:15.441327Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 8, 16, 32, 64, 128, 256]\n"
     ]
    }
   ],
   "source": [
    "print([2**i for i in range(9)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-1.12\n",
    "Python’s random module includes a function choice(data) that returns a\n",
    "random element from a non-empty sequence. The random module in-\n",
    "cludes a more basic function randrange, with parameterization similar to\n",
    "the built-in range function, that return a random choice from the given\n",
    "range. Using only the randrange function, implement your own version\n",
    "of the choice function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:51:57.888050Z",
     "start_time": "2019-06-20T15:51:57.880735Z"
    }
   },
   "outputs": [],
   "source": [
    "def choice(data: List[Any]) -> Any:\n",
    "    return data[randrange(0, len(data))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T15:52:31.662203Z",
     "start_time": "2019-06-20T15:52:31.654515Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 1, 2)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "choice([1, 2, 3, 4]), choice([1, 2, 3, 4]), choice([1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Creativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.13 \n",
    "Write a pseudo-code description of a function that reverses a list of n\n",
    "integers, so that the numbers are listed in the opposite order than they\n",
    "were before, and compare this method to an equivalent Python function\n",
    "for doing the same thing.\n",
    "\n",
    "这里的hint是`The Python function does not need to be passed the value of n as\n",
    "an argument.`，没有看懂题目的意思...随便写个反转列表的函数吧:-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:17:10.770555Z",
     "start_time": "2019-06-20T16:17:10.766384Z"
    }
   },
   "outputs": [],
   "source": [
    "def reverse(data: List[Any]) -> List[Any]:\n",
    "    n = len(data)\n",
    "    return [data[i] for i in range(n-1, -1, -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:17:17.573623Z",
     "start_time": "2019-06-20T16:17:17.566797Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 3, 2, 1]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse([1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.14\n",
    "Write a short Python function that takes a sequence of integer values and\n",
    "determines if there is a distinct pair of numbers in the sequence whose\n",
    "product is odd."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:24:45.610058Z",
     "start_time": "2019-06-20T16:24:45.596172Z"
    }
   },
   "outputs": [],
   "source": [
    "def odd_pair(data: List[int]) -> bool:\n",
    "    odd_nums = {num for num in data if not is_even(num)}\n",
    "    return True if len(odd_nums)>=2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:24:46.046913Z",
     "start_time": "2019-06-20T16:24:46.040602Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "odd_pair([2, 3, 3, 4]), odd_pair([2, 3, 3, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.15\n",
    "Write a Python function that takes a sequence of numbers and determines\n",
    "if all the numbers are different from each other (that is, they are distinct)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:26:56.308575Z",
     "start_time": "2019-06-20T16:26:56.302772Z"
    }
   },
   "outputs": [],
   "source": [
    "def is_unique(data: List[Num]) -> bool:\n",
    "    return len(data) == len(set(data))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-20T16:27:08.983299Z",
     "start_time": "2019-06-20T16:27:08.974577Z"
    }
   },
   "source": [
    "is_unique([1, 2, 3]), is_unique([1, 2, 3, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.16 \n",
    "In our implementation of the scale function (page 25), the body of the loop\n",
    "executes the command data[j] = factor. We have discussed that numeric\n",
    "types are immutable, and that use of the = operator in this context causes\n",
    "the creation of a new instance (not the mutation of an existing instance).\n",
    "How is it still possible, then, that our implementation of scale changes the\n",
    "actual parameter sent by the caller?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">hint: Think about the semantics of data[j] = data[j] ∗ factor.\n",
    "\n",
    "我们通过为原始列表（传入的参数）的每个元素重新赋值来改变参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.17 \n",
    "Had we implemented the scale function (page 25) as follows, does it work\n",
    "properly?\n",
    "```python\n",
    "def scale(data, factor):\n",
    "    for val in data:\n",
    "        val *= factor\n",
    "```\n",
    "Explain why or why not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述函数仅仅新建了一个`local variable`——`val`， 其不断改变，但是不影响`data`本身。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.18 \n",
    "Demonstrate how to use Python’s list comprehension syntax to produce\n",
    "the list [0, 2, 6, 12, 20, 30, 42, 56, 72, 90]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观察数列，找规律：\n",
    "\n",
    "$$a_0  = 0$$\n",
    "$$a_1  = a_0 + 2 \\cdot 1$$\n",
    "$$a_2  = a_1 + 2 \\cdot 2$$\n",
    "$$\\vdots $$\n",
    "$$a_n  = a_{n-1} + 2 \\cdot (n-1)$$\n",
    "\n",
    "得到：\n",
    "$$a_n = n \\cdot (n+1)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T00:40:39.373860Z",
     "start_time": "2019-06-21T00:40:39.369537Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 6, 12, 20, 30, 42, 56, 72, 90]\n"
     ]
    }
   ],
   "source": [
    "print([n * (n+1) for n in range(0, 10)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.19\n",
    "Demonstrate how to use Python’s list comprehension syntax to produce\n",
    "the list [ a , b , c , ..., z ], but without having to type all 26 such\n",
    "characters literally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T00:44:17.042364Z",
     "start_time": "2019-06-21T00:44:17.035645Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n"
     ]
    }
   ],
   "source": [
    "print([chr(ord('a')+i) for i in range(0, 26)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.20\n",
    "Python’s random module includes a function shuffle(data) that accepts a\n",
    "list of elements and randomly reorders the elements so that each possi-\n",
    "ble order occurs with equal probability. The random module includes a\n",
    "more basic function randint(a, b) that returns a uniformly random integer\n",
    "from a to b (including both endpoints). Using only the randint function,\n",
    "implement your own version of the shuffle function.\n",
    "\n",
    "这个题目和leetcode中`Shuffle an Array[384, M]`大概是一致的，这里重现一下Python内部实现`shuffle`的`Fisher-Yates Algorithm`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:10:16.070754Z",
     "start_time": "2019-06-21T01:10:16.055855Z"
    }
   },
   "outputs": [],
   "source": [
    "def shuffle(data: List[Any]) -> None:\n",
    "    n = len(data)\n",
    "    for i in range(n-1, 0, -1):\n",
    "        j = randint(0, i-1)\n",
    "        data[i], data[j] = data[j], data[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:10:20.782362Z",
     "start_time": "2019-06-21T01:10:20.777198Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 1, 2, 3]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = [1, 2, 3, 4]\n",
    "shuffle(l1)\n",
    "l1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.21\n",
    "Write a Python program that repeatedly reads lines from standard input\n",
    "until an EOFError is raised, and then outputs those lines in reverse order\n",
    "(a user can indicate end of input by typing ctrl-D)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:32:26.366493Z",
     "start_time": "2019-06-21T01:32:26.348434Z"
    }
   },
   "outputs": [],
   "source": [
    "def print_reverse() -> None:\n",
    "    lines = []\n",
    "    while 1:\n",
    "        try:\n",
    "            line = input(\"input something: \")\n",
    "        except EOFError:\n",
    "            break\n",
    "        lines.append(line)\n",
    "    print(\"\\n\")\n",
    "    for line in reversed(lines):\n",
    "        print(line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.22\n",
    "Write a short Python program that takes two arrays a and b of length n\n",
    "storing int values, and returns the dot product of a and b. That is, it returns\n",
    "an array c of length n such that c[i] = a[i] · b[i], for i = 0, . . . , n − 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:41:32.451373Z",
     "start_time": "2019-06-21T01:41:32.447132Z"
    }
   },
   "outputs": [],
   "source": [
    "def array_product(a: List[int], b: List[int]) -> List[int]:\n",
    "    return [i * j for i, j in zip(a, b)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:41:51.626301Z",
     "start_time": "2019-06-21T01:41:51.621068Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 12, 30]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array_product([1, 3, 5], [2, 4, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.23\n",
    "Give an example of a Python code fragment that attempts to write an ele-\n",
    "ment to a list based on an index that may be out of bounds. If that index\n",
    "is out of bounds, the program should catch the exception that results, and\n",
    "print the following error message:\n",
    "“Don’t try buffer overflow attacks in Python!”"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:46:01.359032Z",
     "start_time": "2019-06-21T01:46:01.349608Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_overflow() -> None:\n",
    "    data = [1, 2, 3]\n",
    "    try:\n",
    "        data[3] = 0\n",
    "    except IndexError:\n",
    "        print(\"Don’t try buffer overflow attacks in Python!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:46:01.756108Z",
     "start_time": "2019-06-21T01:46:01.749846Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Don’t try buffer overflow attacks in Python!\n"
     ]
    }
   ],
   "source": [
    "check_overflow()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.24\n",
    "Write a short Python function that counts the number of vowels in a given\n",
    "character string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:50:05.655908Z",
     "start_time": "2019-06-21T01:50:05.645740Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_vowels(data: str) -> int:\n",
    "    vowels = 'aeiou'\n",
    "    #vowels = ['a', 'e', 'i', 'o', 'u']\n",
    "    return len([i for i in data.lower() if i in vowels])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:50:05.971718Z",
     "start_time": "2019-06-21T01:50:05.966316Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_vowels('hello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.25\n",
    "Write a short Python function that takes a string s, representing a sentence,\n",
    "and returns a copy of the string with all punctuation removed. For exam-\n",
    "ple, if given the string \"Let s try, Mike.\", this function would return\n",
    "\"Lets try Mike\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:55:00.080464Z",
     "start_time": "2019-06-21T01:55:00.065306Z"
    }
   },
   "outputs": [],
   "source": [
    "# 注意留下空格\n",
    "def remove_punctuation(sentence: str) -> str:\n",
    "    removed = [char for char in sentence \n",
    "                if (ord('A') <= ord(char) <= ord('z')) or ord(char) == ord(' ')]\n",
    "    return ''.join(removed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T01:56:59.071716Z",
     "start_time": "2019-06-21T01:56:59.057551Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Lets try Mike'"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_punctuation(\"Let's try, Mike.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.26\n",
    "Write a short program that takes as input three integers, a, b, and c, from\n",
    "the console and determines if they can be used in a correct arithmetic\n",
    "formula (in the given order), like “a + b = c,” “a = b − c,” or “a ∗ b = c.”"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:24:53.549543Z",
     "start_time": "2019-06-21T02:24:53.537692Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_op_right() -> bool:\n",
    "    nums = input(\"input int a, b, c: \")\n",
    "    operators = '+-*/'\n",
    "\n",
    "    # case1: a = b op c\n",
    "    a, b_c_str = re.findall(r'(\\d+), (\\d+, \\d+)', nums)[0]\n",
    "    case1 = [int(a) == eval(b_c_str.replace(', ', op)) for op in operators]\n",
    "    result = sum(case1)\n",
    "    \n",
    "    # case2: a op b = c\n",
    "    a_b_str, c = re.findall(r'(\\d+, \\d+), (\\d+)', nums)[0]\n",
    "    case2 = [int(c) == eval(a_b_str.replace(', ', op)) for op in operators]\n",
    "    result += sum(case2)\n",
    "\n",
    "    return result > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:25:31.081140Z",
     "start_time": "2019-06-21T02:25:23.784023Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input int a, b, c: 1, 2, 3\n",
      "input int a, b, c: 12, 7, 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_op_right(), check_op_right()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.27\n",
    "In Section 1.8, we provided three different implementations of a generator\n",
    "that computes factors of a given integer. The third of those implementa-\n",
    "tions, from page 41, was the most efficient, but we noted that it did not\n",
    "yield the factors in increasing order. Modify the generator so that it reports\n",
    "factors in increasing order, while maintaining its general performance ad-\n",
    "vantages.\n",
    "\n",
    "注意下生成器type hint的写法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:45:16.774059Z",
     "start_time": "2019-06-21T02:45:16.764190Z"
    }
   },
   "outputs": [],
   "source": [
    "def factors(n: int) -> Generator[int, None, None]:\n",
    "    k = 1\n",
    "    larger_factors = []\n",
    "    while k*k < n:\n",
    "        if n % k == 0:\n",
    "            yield k\n",
    "            larger_factors.append(n // k)\n",
    "        k += 1\n",
    "    if k * k == n:\n",
    "        yield k\n",
    "    for num in reversed(larger_factors):\n",
    "        yield num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:45:18.422599Z",
     "start_time": "2019-06-21T02:45:18.416189Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 10, 20, 25, 50, 100]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(factors(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-1.28 \n",
    "The p-norm of a vector v = (v 1 , v 2 , . . . , v n ) in n-dimensional space is de-\n",
    "fined as:\n",
    "$$\n",
    "\\|v\\|=\\sqrt[p]{v_{1}^{p}+v_{2}^{p}+\\cdots+v_{n}^{p}}\n",
    "$$\n",
    "\n",
    "For the special case of p = 2, this results in the traditional Euclidean\n",
    "norm, which represents the length of the vector. Give an implemen-\n",
    "tation of a function named norm such that norm(v, p) returns the p-norm\n",
    "value of v and norm(v) returns the Euclidean norm of v. You may assume\n",
    "that v is a list of numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:56:09.284541Z",
     "start_time": "2019-06-21T02:56:09.280679Z"
    }
   },
   "outputs": [],
   "source": [
    "def norm(v: List[Num], p: int=2) -> Num:\n",
    "    return sum(i**p for i in v) ** (1/p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T02:56:22.162567Z",
     "start_time": "2019-06-21T02:56:22.157934Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norm([4, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Projects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### P-1.29 \n",
    "Write a Python program that outputs all possible strings formed by using\n",
    "the characters c , a , t , d , o , and g exactly once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T03:37:23.301880Z",
     "start_time": "2019-06-21T03:37:23.293882Z"
    }
   },
   "outputs": [],
   "source": [
    "def add_char(char: str, string_list: List[str]) -> List[str]:\n",
    "    return [char + string for string in string_list]\n",
    "\n",
    "def flatten_lists(lists:List[List[Any]]) -> List[Any]:\n",
    "    result = []\n",
    "    for l1 in lists:\n",
    "        result += l1\n",
    "    return result\n",
    "\n",
    "def permutation(chars: str) -> List[str]:\n",
    "    # Base case\n",
    "    if len(chars) == 1:\n",
    "        return [chars]\n",
    "    return flatten_lists([add_char(chars[i], permutation(chars[:i] + chars[i+1: ])) \n",
    "                            for i in range(len(chars))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T03:38:20.033801Z",
     "start_time": "2019-06-21T03:38:20.022956Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'acb', 'bac', 'bca', 'cab', 'cba']"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 3! = 3 * 2 * 1 = 6\n",
    "permutation('abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### P-1.30\n",
    "Write a Python program that can take a positive integer greater than 2 as\n",
    "input and write out the number of times one must repeatedly divide this\n",
    "number by 2 before getting a value less than 2.\n",
    "\n",
    ">可以直接用`math.log(n, 2)`，不过这里根据hint，尝试下递归的写法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T04:07:32.576214Z",
     "start_time": "2019-06-21T04:07:32.572524Z"
    }
   },
   "outputs": [],
   "source": [
    "def my_log(n: int) -> int:\n",
    "    if n < 2:\n",
    "        return 0\n",
    "    elif n < 4:\n",
    "        return 1\n",
    "    return 1 + my_log(n / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-06-21T04:07:57.806198Z",
     "start_time": "2019-06-21T04:07:57.794235Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 2)"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_log(8), my_log(7.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以下Project暂略。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "273.2px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
